package com.mystudy.leetcode.contest.p_5148;

import com.mystudy.leetcode.base.TreeNode;

import java.util.Stack;

/**
 * @author 周志龙
 * @Email 15216876513@163.com
 * @Date on 2019/8/4 11:23
 * @Description 二叉树着色游戏
 */
public class Solution {
    public boolean btreeGameWinningMove(TreeNode root, int n, int x) {
        //遍历x有多少子节点
        Stack<TreeNode> stack = new Stack();
        stack.push(root);
        TreeNode xNode = null;
        while (!stack.isEmpty()) {
            TreeNode pop = stack.pop();
            if (pop.val == x) {
                xNode = pop;
                break;
            }
            if (pop.left != null) {
                stack.push(pop.left);
            }
            if (pop.right != null) {
                stack.push(pop.right);
            }
        }
        //遍历获取x所有子节点
        int xCount = 1;
        xCount = postOrder(xNode);

        return n - xCount > xCount;
    }

    private int postOrder(TreeNode node) {
        if (node == null) {
            return 0;
        }

        int leftCount = postOrder(node.left);
        int rightCount = postOrder(node.right);
        return leftCount + rightCount + 1;
    }

}
